package leetcode;

public class TargetSum {

	public static void main(String[] args) {
		TargetSum object = new TargetSum();
		int[] nums = {1, 1, 1, 1, 1};
		System.out.println(object.findTargetSumWays(nums, 3));
	}
	
	//460ms
	//还有一些s > sum(nums) 的这些边界条件不知道是否处理了
	public int findTargetSumWays(int[] nums, int S) {
		if(nums == null || nums.length <= 0){
			return 0;
		}
		int length = nums.length;
		int total = 1 << length;
		int[] dp = new int[total];
		dp[0] = -nums[0];
		dp[1] = nums[0];
		for(int i = 1; i < length; i++){
			int cur = 1 << i;
			for(int j = cur, k = 0; j < cur * 2; j++, k++){
				dp[j] = dp[k] + nums[i];
			}
			for(int j = 0; j < cur; j++){
				dp[j] = dp[j] - nums[i];
			}
		}
		int res = 0;
		for(int j = 0; j < total; j++){
			//System.out.print(dp[j] + "  ");
			if(dp[j] == S){
				res++;
			}
		}
//		System.out.println();
//		System.out.println(res);
        return res;
    }
	
//	The recursive solution is very slow, because its runtime is exponential
//
//	The original problem statement is equivalent to:
//	Find a subset of nums that is positive, and the rest of them negative, such that the sum is equal to target
//
//	Let P be the positive subset and N be the negative subset
//	For example:
//	Given nums = [1, 2, 3, 4, 5] and target = 3 then one possible solution is +1-2+3-4+5 = 3
//	Here positive subset is P = [1, 3, 5] and negative subset is N = [2, 4]
//
//	Then let's see how this can be converted to a subset sum problem:
//
//	                  sum(P) - sum(N) = target
//	sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
//	                       2 * sum(P) = target + sum(nums)
//	So the original problem has been converted to a subset sum problem as follows:
//	Find a subset P of nums such that sum(P) = (target + sum(nums)) / 2
//
//	Note that the above formula has proved that target + sum(nums) must be even
//	We can use that fact to quickly identify inputs that do not have a solution 
//	For detailed explanation on how to solve subset sum problem, you may refer to Partition Equal Subset Sum
	
	
	//runtime : 19ms
	public int findTargetSumWays_2(int[] nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        if(S > sum || (sum + S) % 2 == 1)   return 0;
        return subsetSum(nums, (sum + S) >> 1);
    }

	private int subsetSum(int[] nums, int sum) {
		//和为j子集的个数
		int[] dp = new int[sum + 1];
		// dp init
		dp[0] = 1;
		// dp transition
		for (int i = 0; i < nums.length; i++) {
			//注意，这里要从右往左遍历，因为需要的是小于或者等于j的dp值
			//如果从左往右遍历，可能会更新j的值，比如j = 2的时候，进行了更新
			//后面需要计算4的时候，dp[4 - 2]可能会用到j = 2，造成错误
			
			//而从右往左更新的时候是更新的大值，后面肯定不会用到该值
			for (int j = sum; j >= nums[i]; j--) {
				//因为j 小于nums[i]的时候dp[i][j] = dp[i - 1][j]也就是说不用更新
				dp[j] = dp[j] + dp[j - nums[i]];
			}
		}
		return dp[sum];
	}
}
